<?php
  /**------------------------------------------------------------------------------
   * Title:        BNF Parser
   * Filename:     parser.class.php
   * Version:      0.3
   * Author:       Richard Keizer
   * Email:        ra dot keizer at gmail dot com
   *-------------------------------------------------------------------------------
   * COPYRIGHT (c) 2011 Richard Keizer
   *
   * The source code included in this package is free software; you can
   * redistribute it and/or modify it under the terms of the GNU General Public
   * License as published by the Free Software Foundation. This license can be
   * read at:
   *
   * http://www.opensource.org/licenses/gpl-license.php
   *
   * This program is distributed in the hope that it will be useful, but WITHOUT
   * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
   * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
   *------------------------------------------------------------------------------
   *
   * note: I did not study parsers, lexers etc. This is just my interpretation.
   *
   * changes:
   *  0.1   - initial release
   *  0.2   - semantisized code
   *  0.3   - parsetree is generated as a DOMDocument
   *
   * todos:
   *  - convert grammar to XML-grammar
   *  - validation + error handling
   *
   */
  
  class Parser {
    protected $grammar;
    protected $lexer;
    protected $parsetree;
    
    public function __construct(Grammar $grammar, Lexer $lexer) {
      $this->grammar = $grammar;
      $this->lexer = $lexer;
    }
    
    public function createParsetree() {
      $this->parsetree = new DOMDocument("1.0", "UTF-8");
      $this->parsetree->formatOutput = true;
      
      if ($result = $this->match()) $this->parsetree->appendChild($result);
      return $this->parsetree;
    }
    
    protected function match($lhs='root', $cursor=0) {
      $startcursor = $cursor;
      $maxcursor = $cursor;
      
      $result = FALSE;
      
      foreach ($this->grammar->getRulesByLHS($lhs) as $rule) {
        $cursor = $startcursor;
        
        $tmp = $this->parsetree->createDocumentFragment();
        foreach ($rule->getSymbols() as $symbol) {
          if (!$symbol->isTerminal()) {
            $match = $this->match($symbol->getName(), $cursor);
          } elseif (preg_match("/^{$symbol->getName()}$/sm", $token=$this->lexer->getToken($cursor))) {
            $match = $this->parsetree->createDocumentFragment();
            $c = $this->parsetree->createElement('token', $token);
            $match->appendChild($c);
            $c->setAttribute('gain', 1);
          } else {
            $match = FALSE;
          }
          if (!$match) break;
          
          $c = $tmp->appendChild($match);
          $cursor += $c->getAttribute('gain');
          $c->removeAttribute('gain');
        }
        
        if ($tmp->hasChildNodes()) {
          //use highest gain... maybe we should check for smallest depth too?
          if ($cursor > $maxcursor) {
            $maxcursor = $cursor;
            $result = $this->parsetree->createDocumentFragment();
            $c = $this->parsetree->createElement($lhs);
            $result->appendChild($c);
            $c->setAttribute('gain', $maxcursor - $startcursor);
            $c->appendChild($tmp);
          }
        }
      }
      return $result;
    }
  }
  

  abstract class Lexer {
    protected $tokens = array();
    
    public function __construct($input) {
      $this->tokens = $this->tokenize($input);
    }
    
    public function tokenCount() {
      return count($this->tokens);
    }
    
    public function getToken($i) {
      return array_key_exists($i, $this->tokens) ? $this->tokens[$i] : false;
    }
    
    abstract protected function tokenize($text);
  }
  
  class Symbol {
    protected $isTerminal;
    protected $name;
    
    public function __construct($name) {
      $name = trim($name);
      $this->isTerminal = ($name[0] == "'");
      $this->name = trim($name, "'");
    }
    
    public function isTerminal() {
      return $this->isTerminal;
    }
    
    public function getName() {
      return $this->name;
    }
  }
  
  class Rule {
    protected $LHS;
    protected $symbols = array();
    
    public function __construct($rule) {
      $sides = preg_split("/\s*::=\s*/smi", $rule);
      $this->LHS = $sides[0];
      $this->symbols = $this->splitRHSintoSymbols($sides[1]);
    }
    
    protected function splitRHSintoSymbols($text) {
      $result = array();
      foreach (preg_split("/\s+/smi", $text) as $symbol)
      $result[] = new Symbol($symbol);
      return $result;
    }
    
    public function getLHS() {
      return $this->LHS;
    }
    
    public function getSymbols() {
      return $this->symbols;
    }
  }
  
  class Grammar {
    protected $rules = array();
    
    public function __construct($text) {
      $this->parseRules($text);
    }
    
    protected function parseRules($text) {
      $this->rules = array();
      foreach (preg_split("/\R/", $text) as $rule) {
        if ($rule) {
          $rule = new Rule($rule);
          $this->rules[$rule->getLHS()][] = $rule;
        }
      }
    }
    
    public function getRulesByLHS($lhs) {
      return $this->rules[$lhs];
    }
  }
  

